package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.org.apache.xml.internal.security.keys.content.RetrievalMethod;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
	 Implement the following operations of a queue using stacks.

    push(x) -- Push element x to the back of queue.
    pop() -- Removes the element from in front of queue.
    peek() -- Get the front element.
    empty() -- Return whether the queue is empty.

	Notes:

    You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
    Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
    You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

题目大意
	 用栈来实现队列
解题思路
	（1）题意为用栈来实现队列。

（2）要用栈来实现队列，首先需要了解栈和队列的性质。栈：先进后出，只能在栈顶增加和删除元素；队列：先进先出，只能在队尾增加元素，从队头删除元素。这样，用栈实现队列，就需要对两个栈进行操作，这里需要指定其中一个栈为存储元素的栈，假定为stack2，另一个为stack1。当有元素加入时，首先判断stack2是否为空（可以认为stack2是目标队列存放元素的实体），如果不为空，则需要将stack2中的元素全部放入(辅助栈)stack1中，这样stack1中存储的第一个元素为队尾元素；然后，将待加入队列的元素加入到stack1中，这样相当于实现了将入队的元素放入队尾；最后，将stack1中的元素全部放入stack2中，这样stack2的栈顶元素就变为队列第一个元素，对队列的pop和peek的操作就可以直接通过对stack2进行操作即可。

（3）详情见下方代码。希望本文对你有所帮助。
 * @Date 2017-09-26 00：22
 */
public class _232_Implement_Queue_using_Stacks {
	
	LinkedList<Integer> stack1 = new LinkedList<Integer>();
	LinkedList<Integer> stack2 = new LinkedList<Integer>();		//真正存储的队列
	
    /** Initialize your data structure here. */
    public _232_Implement_Queue_using_Stacks() {
        
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
    	while (!stack2.isEmpty()) {
    		stack1.addLast(stack2.removeLast());
    	}
    	stack1.addLast(x);
    	while (!stack1.isEmpty()) {
    		stack2.addLast(stack1.removeLast());
    	}
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
    	return stack2.removeLast();
    }
    
    /** Get the front element. */
    public int peek() {
    	return stack2.getLast();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
    	return stack2.isEmpty();
    }
    
	public static void main(String[] args) {
		_232_Implement_Queue_using_Stacks obj = new _232_Implement_Queue_using_Stacks();
//		obj.twoSum(new int[]{1, 2, 3, 4, 5, 6, 7}, 7);
//		obj.twoSum2(new int[]{2, 7, 11, 15}, 9);

	}

}
